/*
 * @Author: xujianwei
 * @Date: 2021-11-15 11:55:19
 * @LastEditors: xujianwei
 * @LastEditTime: 2021-11-16 11:43:43
 */

 
// 1. 从第一个元素开始，该元素可以认为已经被排序；
// 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
// 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
// 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
// 5. 将新元素插入到该位置后；
// 6. 重复步骤2~5。


export default function(array){
    // 查找插入位置时使用二分查找的方式
    for (var i = 1; i < array.length; i++) {
        var key = array[i], left = 0, right = i - 1;
        while (left <= right) {
            var middle = parseInt((left + right) / 2);
            if (key < array[middle]) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        for (var j = i - 1; j >= left; j--) {
            array[j + 1] = array[j];
        }
        array[left] = key;
    }
    return array;
   
}